0967. 连续差相同的数字【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - BFS

1. 📝 题目描述

• leetcode

返回所有长度为 n 且满足其每两个连续位上的数字之间的差的绝对值为 k 的非负整数。

请注意，除了数字 0 本身之外，答案中的每个数字都不能有前导零。例如，01 有一个前导零，所以是无效的；但 0 是有效的。

你可以按任何顺序返回答案。

---

示例 1：

输入：n = 3, k = 7
输出：[181,292,707,818,929]

解释：
注意，070 不是一个有效的数字，因为它有前导零。

---

示例 2：

输入：n = 2, k = 1
输出：[10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

---

示例 3：

输入：n = 2, k = 0
输出：[11,22,33,44,55,66,77,88,99]

---

示例 4：

输入：n = 2, k = 2
输出：[13,20,24,31,35,42,46,53,57,64,68,75,79,86,97]

---

提示：

• 2 <= n <= 9
• 0 <= k <= 9

2. 🎯 s.1 - BFS

js

/**
 * @param {number} n
 * @param {number} k
 * @return {number[]}
 */
var numsSameConsecDiff = function (n, k) {
  // 特殊情况：n = 1 时，返回 0-9
  if (n === 1) return [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

  // BFS：从 1-9 开始（避免前导零）
  let queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]

  // 逐位构建数字，共需要 n-1 次迭代
  for (let i = 1; i < n; i++) {
    const nextQueue = []

    for (const num of queue) {
      const lastDigit = num % 10

      // 尝试添加 lastDigit + k
      if (lastDigit + k <= 9) {
        nextQueue.push(num * 10 + lastDigit + k)
      }

      // 尝试添加 lastDigit - k（避免 k=0 时重复）
      if (k !== 0 && lastDigit - k >= 0) {
        nextQueue.push(num * 10 + lastDigit - k)
      }
    }

    queue = nextQueue
  }

  return queue
}

• 时间复杂度：$O(2^n)$，最坏情况下每个数字可以扩展为两个数字，共扩展 n-1 次
• 空间复杂度：$O(2^n)$，队列中最多存储 $2^n$ 个数字

算法思路：

• BFS 逐位构建：从 1-9 开始（避免前导零），逐位添加满足条件的数字，构建长度为 n 的数字
• 队列初始化：将 1-9 加入队列作为第一位数字
• 扩展规则：对于当前数字的最后一位 lastDigit，可以添加 lastDigit+k 或 lastDigit-k 作为下一位（需满足 0-9 范围）
• 去重处理：当 k=0 时，lastDigit+k 和 lastDigit-k 相同，只添加一次避免重复
• 迭代次数：共进行 n-1 次迭代，每次将队列中的数字扩展一位
• 特殊情况：n=1 时直接返回 [0,1,2,3,4,5,6,7,8,9]，因为单个数字都满足条件